package 排序算法.快速排序;

import java.util.Arrays;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.快速排序
 * @ClassName: Quicksort
 * @Author: zhouyihe
 * @Date: 2025/11/5 10:10
 * @Description: 快速排序-递归实现 选择最左侧的元素作为基准-选随机元素作为基准-三数取中法取基准
 */
public class Quicksort {
    /**
     * 快速排序
     * 优点:
     * 平均情况下非常高效，时间复杂度为 O(nlogn)
     * 原地排序，空间复杂度低
     * 缓存友好，数据局部性好
     * 适合处理大规模数据
     * 缺点:
     * 最坏情况下性能退化至 O(n²)，比如当数组已经排序时
     * 不稳定的排序算法
     * 对于小数组，快速排序可能比其他基础排序慢
     * 递归实现可能导致栈溢出（可以使用迭代方式解决）
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区位置

            // 选择最左侧的元素作为基准
            // int pivotIndex = partition(arr, low, high);

            // 每次都选择最左侧的元素作为基准,可能会在数组已经排序或接近排序时导致最坏性能，随机选择基准可以降低这种风险：
            //int pivotIndex = randomPartition(arr, low, high);

            // 三数取中法--选择左中右三个元素的中值作为基准,可以减进一步优化
            int pivotIndex = medianOfThreePartition(arr, low, high);

            // 递归排序左右子数组
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 三数取中法
    private static int medianOfThreePartition(int[] arr, int low, int high) {
        int mid = low + (high - low) >> 1;

        // 对三个元素进行排序
        if (arr[mid] < arr[low])
            swap(arr, mid, low);
        if (arr[high] < arr[low])
            swap(arr, high, low);
        if (arr[high] < arr[mid])
            swap(arr, high, mid);

        // 将中值（现在在arr[mid]）放到arr[low]
        swap(arr, mid, low);

        // 使用标准分区过程
        return partition(arr, low, high);
    }

    // 交换元素位置
    private static void swap(int[] arr, int i, int j) {
        // 这个交换方式仅限于i和j不相等的情况下
        // arr[i] = arr[i] ^ arr[j];
        // arr[j] = arr[i] ^ arr[j];
        // arr[i] = arr[i] ^ arr[j];
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 随机选择基准
    private static int randomPartition(int[] arr, int low, int high) {
        // 随机选择基准
        int pivotIndex = (int) (Math.random() * (high - low + 1)) + low;

        // 将随机选择的元素放到最左侧
        int temp = arr[pivotIndex];
        arr[pivotIndex] = arr[low];
        arr[low] = temp;

        // 调用标准分区过程
        return partition(arr, low, high);
    }

    public static int partition(int[] arr, int low, int high) {
        // 选择最左侧元素作为基准
        int pivot = arr[low];
        int i = low + 1;

        for (int j = low + 1; j <= high; j++) {
            // 将小于基准的元素移到左侧
            if (arr[j] < pivot) {
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }

        // 将基准元素放到正确的位置
        int temp = arr[low];
        arr[low] = arr[i - 1];
        arr[i - 1] = temp;

        return i - 1;
    }

    // 计数器和测试法
    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            quickSort(arr1, 0, arr1.length - 1);
            Arrays.sort(arr2);
            if (!isEqual(arr1, arr2)) {
                System.out.println("出错了！");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
